package com.cat.dataStructure02;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-performance-of-a-team/description/
 * @create 2025/10/27 21:21
 * @since JDK17
 */

public class Solution73 {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        long ans = 0, sum = 0;
        int N = ((int) (1e9 + 7));
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i] = new int[]{efficiency[i], speed[i]};
        }
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = n - 1; i >= n - k; i--) {
            sum += arr[i][1];
            heap.add(arr[i][1]);
            ans = Math.max(ans, arr[i][0] * sum);
        }
        for (int i = n - k - 1; i >= 0; i--) {
            if (arr[i][1] > heap.peek()) {
                sum += arr[i][1] - heap.poll();
                heap.add(arr[i][1]);
            }
            ans = Math.max(ans, sum * arr[i][0]);
        }

        return ((int) (ans % N));
    }
}
